Previous | Index | Next |

Hash Tables

The following table gives the requirements beyond the base requirements for hashed associated containers (hash tables). In this table b is and integer and h is a hash function.

Hashed associative container requirements (in addition to base requirements).
expression return type assertion/note
pre/post-condition
complexity
X() . constructs an empty container;
uses HashFunction api as the hash function and PredEqual api as the key comparison; builds at least 1000 buckets.
constant
X(i, j) . constructs an empty container and inserts elements from the range [i,j) into it;
uses defaults for HashFunction and key comparison.
expected O(N) where N is the distance from i to j)
a_uniq.insert(t) Pair as base requirements. expected constant
a_eq.insert(t) iterator as base requirements. expected constant
a.insert(i, j) void as base requirements. expected O(N) where N is the distance from i to j.
a.erase(k) int as base requirements. expected O(count(k))
a.erase(q1, q2) void as base requirements. expected O(N) (N is the distance from q1 to q2).
a.find(k) as base requirements. as base requirements. expected contants
a.equal_range(k) as base requirements. as base requirements. expected O(N) (N is the number of elements having key key).
a.count(k) int as base requirements. expected O(count(k))

For hash tables, iteration through the table present the keys in no particular order; the actual order depends on the order of insertion, the number os hash buckets, and on the hash function. Table entries which have equal keys will appear consecutively when iterating through the table. Iterators and references remain valid after all operations but ranges such as the result of equal_range may no longer be valid.

The hash function is expected to accept a single object, the key, and return a integer. The ability of the implementation to achive expected constant time performance depends on the ability of the hashing function to hash key values evenly across a large range of integers,


Previous | Index | Next |